Automatic categorizing of texts based on content generally begins with a list of key words and typically follows one of three general strategies, i.e., a vector space strategy, a statistical strategy and a Bayesian strategy.
Vector Space Strategy
The vector space strategy generally reduces each text to a set of counts, e.g., counts of key words appearing in the text. Following this strategy, the counts, organized as vectors, are subjected to standard mathematical devices used to define properties relating to the vectors, such as the distance between any two vectors or the angle between any two vectors. These distances or angles become the starting point for assigning centers to known categories and for estimating similarity between an uncategorized text and the known categories of texts. An important point is that key mechanisms of the vector space strategy are borrowed from well-known mathematics. The empirical validity of the particular mathematical devices used as models of texts is assumed without investigation.
Vector models, like singular value decomposition, substitute mathematical assumptions for empirically derived models of text. Where each text might be represented by a vector, such as a vector of counts or a vector of proportions, the measure of association between such vectors (or between such vectors and vectors that represent categories) is derived from implicit mathematical assumptions, usually assuming that the space in which the vectors are embedded is Euclidean That is, where the association between two vectors is represented by the cosine of the angle between them, this representation (if it uses the conventional Euclidean definition of a cosine) assumes a Euclidean space. Similarly, where the association between two vectors is represented by the length of a difference vector, this “length” typically assumes a Euclidean space. By failing to test the validity of their assumptions against data, the vector space techniques incorporate error or, at the least, untested assumptions, into their devices for producing categories. For example, where “distance” per se is capable of many realizations, these models usually assume Euclidean distance and Euclidean angles. These are assumptions that new research has shown to be in error. In contrast, the strategy of the present invention, i.e., the “Levine strategy,” makes no false geometrical or dimensional assumptions about the space under consideration, or avoids these assumptions altogether. The Levine strategy is described below in detail.
Statistical Strategy
The statistical strategy, like the vector space strategy, reduces a text to a set of counts. The statistical strategy characterizes categories of texts and heterogeneity within categories by standard statistical devices like means, sums of squared deviations, standard deviations, and standardized scores. These devices are borrowed from well known statistical procedures. Their empirical validity as descriptive devices is assumed. (These devices are essentially equivalent to the distances of the vector space strategy).
Statistical strategies substitute standard statistical devices for testable assumptions, generally using and assuming the validity of least squares and the implied means, variances, and standard deviations that are part of the least squares strategy. These are assumptions that new research has shown to be invalid relative to categorizing texts. In contrast, the Levine strategy of the present invention separates the model from statistical devices used to assess the fit of the model to the data.
Bayesian Strategy
Bayesian strategy in practice represents a document by noting the presence or absence of previously determined key words, like the key word “impotence”, which is often indicative of “spam” mail. The device of the Bayesian strategy employs the logic of Bayes' theorem, which directs the computation of the probability that an uncategorized text is “caused” by (or generated by) each of the target categories—given the prior probabilities and the properties of the uncategorized document. Categorization is effected by weighted comparison of the probabilities with respect to each of the possible categories of the text.
There are at least two shortcomings of conventional implementations of the Bayesian strategy. First, Bayesian filters generally rely on probabilities that are context dependent. For example, in an email spam filter context, if a person's email is 99% spam, then the prior probability that an uncategorized message is spam is 0.99 regardless of content. For this person, the presence of the word “impotence” in a document boosts the probability that it is spam into the 0.99 to 1.0 range. For a person whose email is 1% spam, the probability that an uncategorized message is spam is 0.01 without testing for key words. For this person, the presence of the word “impotence” in a message boosts the probability into the 0.01 to 1.0 range. Thus, the true prior probabilities, as well as the cut point at which a method may be safely and reasonably estimated to have been spam, are highly variable. This places a premium on customization that is a mixed blessing for generalized applications. For example, this high variability would cause a problem for a Bayesian spam filter employed at a server level when many email users are served by the same server. What is needed is an automatic text categorizing system that does not depend on the relative proportion of spam or non-spam within the sample.
The second general problem of the Bayesian strategy lies in the gap between theory and practical application. In theory, the Bayesian strategy depends on Bayes' theorem to provide the probability that a message was spam given the presence or absence in that message of key words. The problem with this is that a theoretically correct implementation of Bayes' theorem is difficult to put into practice. If, for example, a Bayesian filter is to use n key words (reduced from the full text), the theory requires an estimate of the prior probability of spam for each of the 2n compound events that correspond to combinations (present and absent) of the n key words. The theorem requires the n probabilities associated with each key word in isolation, plus the probabilities associated with each of the n(n−1)/2 pairs of key words in the absence of the others, plus the probabilities associated with each triple of key words, and so forth. For a value of n greater than 20, i.e., for more than 20 key words, the result is a large number of probabilities that have to be estimated.
In practice this problem is not solved. It is dealt with by assuming that key words are statistically independent. The assumption would, if correct, make the Bayesian theory practical, but it is clearly not true. For example, with spam email this assumption of statistical independence would assume that the probability associated with one of the key words, e.g., “impotence,” is independent of the probability of the word “physician,” and independent of the probability of the word “prescription,” and are independent of the probabilities associated with the other key words. However, these words are not independent. For example, the probability of the word “physician” in a document that uses the word “impotence” is different from the probability of the word “physician” in the absence of the word “impotence.” As a consequence, the probabilities used by so-called Bayesian filters are generally not the probabilities specified by Bayes' theorem.
Thus, suppose that the presence of “impotence” in a message implies a 0.9 probability that the message containing it is spam. Its presence is a good, but not certain, indicator of spam; the message could be a prescription from the person's physician. Suppose further that the presence of the word “physician” in a message implies a 0.9 probability that the message containing it is spam and that the presence of the word “prescription” implies a 0.9 probability that the message containing it is spam. Then, what more do we learn if all three key words are present? The answer is “not much,” because none of these words goes far to address the ambiguities involved in the single word “impotence.” They do nothing to screen out the possibility that the message is a prescription from the person's physician. The probabilities are not independent. The probability that the message with all three key words present is spam is only slightly improved as compared to the probability associated with any one of the key words.
But the Bayesian filters, contrary to fact (for the sake of computational simplicity), assume independence of the key words. This false assumption resolves this combination of information to a near-certainty, p=0.9986, by recourse to what Bayes' theorem would say if the three probabilities were independent corroborating evidence of spam. However, these key words are not independent, with the consequence that the probability that would be used by the so-called Bayesian filter is incorrect (too high). The true probability, which would have to be computed from the data, not from the theorem, is likely to be closer to the original 0.9 than to 0.9986. In contrast, the Levine strategy of the present invention obviates the intractable implications inherent in the logic of probabilities.